package 中等.树;

import util.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一棵二叉树 root，返回所有重复的子树。
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-duplicate-subtrees
 */
public class 寻找重复的子树_652 {

    public static void main(String[] args) {

    }

    private Map<String, Boolean> map = new HashMap<>();

    /**
     * 哈希表+字符串构建子树
     *
     * @param root
     * @return
     */
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();

        dfs(root, list);

        return list;
    }

    /**
     * 递归返回值，构建 node 子树
     * 以 node.val(递归左子树)(递归右子树) 的方式
     */
    public String dfs(TreeNode node, List<TreeNode> list) {
        if (node == null) {
            return "";
        }
        StringBuilder stringBuilder = new StringBuilder();
        String treeStr = stringBuilder.append(node.val)
                .append("(")
                .append(dfs(node.left, list))
                .append(")")
                .append("(")
                .append(dfs(node.right, list))
                .append(")").toString();

        if (map.containsKey(treeStr) && !map.get(treeStr)) {
            list.add(node);
            // 确保出现三次相同子树时，list 中子树唯一
            map.put(treeStr, true);
        }
        // 没有添加到 list 里面过
        if (!map.containsKey(treeStr)) {
            map.put(treeStr, false);
        }
        return treeStr;
    }

}
